Optimale beslisboom

Een beslisboom van m vertakkingen met elk n takken
heeft N=n^m uitkomsten
maar een keuzelast B = n×m

Bij welke n en m is B optimaal? Ofwel
bij welke n en m is B/N minimaal?
🔽 Eerste poging

Dat gaat op als
∂(B/N)/∂n + ∂(B/N)/∂m = 0

We weten dat

B/N = n×m/n^m =

m/n^m-1

dus

∂(B/N)/∂n =
∂(m/n^m-1)/∂n =
∂(m×n^1-m)/∂n =
m×(1-m)×n^1-m-1 =

m(1-m)×n^-m

en

∂(B/N)/∂m =
∂(m/n^m-1)/∂m =
∂(m×n^1-m)/∂m =
∂(m×e^ln(n)(1-m))/∂m =
∂(m×e^{ln(n)-m×ln(n)})/∂m =
∂(mn×e^-mln(n))/∂m =
mn×(∂(e^-mln(n))/∂m) + (∂(mn)/∂m)×e^-mln(n) =
mn×(-ln(n))e^-mln(n) + n×e^-mln(n) =
(-mn×ln(n) + n)n^-m =

(1-m×ln(n))n^1-m

Samenvoegend

∂(B/N)/∂n + ∂(B/N)/∂m =
m(1-m)×n^-m + (1-m×ln(n))n^1-m =
(m(1-m) + n - nm×ln(n))n^-m

en dat moet =0 zijn.
Dus

m(1-m) + n - nm×ln(n) = 0 of n^-m=0 ⇔ m=∞

m(1-m) + n - nm×ln(n) = 0 ⇔
m - m² + n - nm×ln(n) = 0 ⇔
1 - m + n/m - n×ln(n) = 0 ⇔
1 - m = n×ln(n) - n/m ⇔

n(ln(n) - 1/m) / (1 - m) = 1

waar ik ook niet echt blij van word. Volgens ai klopt de berekening wel.

Bij nader inzien is de vraag of ∂(B/N)/∂n + ∂(B/N)/∂m = 0 van toepassing is.
Dat gaat over de gradient.
Voor een minimum moeten zowel ∂(B/N)/∂n = 0 als ∂(B/N)/∂m = 0.
De gradient is ook 0 als ∂(B/N)/∂n = -∂(B/N)/∂m

over n andere boeg dan maar

---

⏶ sluit eerste poging

🔽 Tweede poging

B = n×m en N=n^m ⇔ n=N^1/m en
B = m×N^1/m

Bij vaste N hangt B alleen af van m met een verhoopt optimum als

∂B/∂m = 0 ⇔
∂(m×N^1/m)/∂m = 0 ⇔
∂(m×e^ln(N)/m)/∂m = 0 ⇔
(∂m/∂m)×e^ln(N)/m + m×∂(e^ln(N)/m)/∂m = 0 ⇔
e^ln(N)/m + m×(ln(N)ln(m))e^ln(N)/m = 0 ⇔
(1 + m×(ln(N)ln(m)))e^ln(N)/m = 0 ⇔

(1 + m×(ln(N)ln(m)))=0 of e^ln(N)/m = 0 ⇔ m=∞

1 + m×(ln(N)ln(m)) = 0 ⇔
m×(ln(N)ln(m)) = -1 ⇔
m×ln(m) = -1/ln(N) ⇔

Optimum bestaat alleen bij m>0 en ln(m)<0, dus 0<m<1

m^m = e^-1/ln(N) ⇔
N^ln(m) = e^-1/m

⏶ tweede poging sluiten

🔽 Derde poging

B = n×m en N=n^m ⇔
ln(N)=m×ln(n) ⇔
m= ln(N)/ln(n)

B/N = nm / n^m = n(ln(N)/ln(n)) / n^ln(N)/ln(n)

De noemer vereenvoudigt door er eerst de ln van te nemen

ln(n^ln(N)/ln(n)) =
(ln(N)/ln(n))×ln(n) = ln(N) ⇔

n^ln(N)/ln(n) = N

Dus

B/N = n(ln(N)/ln(n)) / n^ln(N)/ln(n) =
n(ln(N)/ln(n)) / N ⇔ B/N = n×ln(N) / (N×ln(n))

B/N = (n/N)×(ln(N)/ln(n))

of eigenlijk, ontnuchterend

B = n×(ln(N)/ln(n))
en
B/ln(N) = n/ln(n)

⏶ derde poging sluiten

🔽 Te bewijzen valt dat het optimum bij n=e ligt, tussen 2 en 3.

B/ln(N) = n/ln(n)

Dat is minimaal als

$\frac{''d''}{''dn''}$ ($\frac{''n''}{''ln(n)''}$) = 0 ⇔
$\frac{''dn''}{''dn''}$ × $\frac{''1''}{''ln(n)''}$ + n×$\frac{''d''}{''dn''}$ ($\frac{''1''}{''ln(n)''}$) = 0 ⇔
$\frac{''1''}{''ln(n)''}$ + n×$\frac{''d\; ln(n)''}{''dn''}$ × $\frac{''d''}{''d\; ln(n)''}$ ($\frac{''1''}{''ln(n)''}$) = 0 ⇔
$\frac{''1''}{''ln(n)''}$ + n×n^-1 × -(ln(n))^-2 = 0 ⇔
(ln(n))^-1×(1 - (ln(n))^-1) = 0 ⇔
(ln(n))^-1=0 of (ln(n))^-1 = 1 ⇔ ln(n) = 1 ⇔

n = ∞ of n=e

⏶ QED, sluiten

Het dichtsbij e (= 2,718...) zijnde gehele getal is 3. Dus

B = n ln(N)/ln(n) wordt 3 ln(N)/ln(3)

N	$\frac{''ln(N)''}{''ln(3)''}$	B	1/(B/N)
3	1	3	1
9	2	6	1,33
27	3	9	3
81	4	12	6,75
...	...	...	...
21483	9	27	795
...	...	...	...
1000000	100	300	3333

Te vervolgen met een nieuwe list...
Al dit was bedoeld als vervolg op mijn oude blogpost "de-macht-van-zeven". Waarbij de intuitieve aanname lag dat B/N minimaal is bij n waarvoor nⁿ=N

N	n	B	1/(B/N)
1	1	1	1
4	2	4	1
27	3	9	3
256	4	16	16
...	...	...	...
823543	7	49	16,81
...	...	...	...
10000000000	10	100	100000000

In beeld, met N/B(n) voor het B = n ln(N)/ln(n) alternatief staat, en N/B(3) voor B = 3 ln(N)/ln(3):